1. Field of Use
The present invention relates to apparatus used by a cache memory and more particularly to apparatus for replacing information within the locations of such cache memory.
2. Prior Art
It is well known to interpose a cache memory between a central processing unit and main memory. Such arrangements improve the performance of the processing unit by providing fast access to instructions and data stored in the cache or buffer memory. During normal operation, when the instructions or data requested by the processing unit are not stored in cache, the block containing the requested information is fetched from main memory. When the cache memory is filled, new blocks replace old blocks resident therein.
While different arrangements may be used to select old blocks of information, a least recently used (LRU) replacement has been one of the most commonly used schemes employed in cache units. These units include cache memories and address directory circuits. The memories are organized into a number of levels for storing information in the form of data and instructions for fast access. The directory circuits contain address information for identifying which blocks of instructions and data are stored in the cache memory levels. Generally, the LRU replacement scheme has been implemented using a round robin counter or first in first out (FIFO) array. In such arrangements, the assignment of a group or block of locations is made sequentially. A more accurate record of order of block usage is proved in a system which employs a memory for storing a number of least recently used bits to represent the order of usage of memory locations. This system is disclosed in U.S. Pat. No. 4,334,289.
When implemented as an array, the updating of entries can be time-consuming, particularly when there are a large number of cache level entries. Moreover, the delays in updating, reduce cache system performance and result in least recently used approximation. To overcome these difficulties, apparatus which operates as a shifting content addressable memory (CAM) has been used. This apparatus is disclosed in U.S. Pat. No. 4,783,735. While this apparatus reduces delays and is easily constructed in LSI form, it still does not use standard parts in its construction.
Accordingly, it is a primary object of the present invention to provide high speed apparatus for replacing information within a memory on a least recently used (LRU) basis.
It is a further object of the present invention to provide high performance LRU apparatus implementable with standard integrated circuit parts.